#include "lightsout_util.h"

//touch the light at row:col
bitarray press_button(ba_ht_elem B, uint8_t i, int row, int col,
                       uint8_t width, uint8_t height)
{
    //toggle the position i
    bitarray res = bitarray_flip(B->ba, i);
    //toggle the position up to i
    int row0 = row - 1;
    int col0 = col;
    if (is_valid_pos(row0, col0, width, height)) {
        uint8_t i0 = get_index(row0, col0, width, height);
        res = bitarray_flip(res, i0);
    }
    //toggle the position down to i
    int row1 = row + 1;
    int col1 = col;
    if (is_valid_pos(row1, col1, width, height)) {
        uint8_t i1 = get_index(row1, col1, width, height);
        res = bitarray_flip(res, i1);
    }
    //toggle the position left to i
    int row2 = row;
    int col2 = col - 1;
    if (is_valid_pos(row2, col2, width, height)) {
        uint8_t i2 = get_index(row2, col2, width, height);
        res = bitarray_flip(res, i2);
    }
    //toggle the position right to i
    int row3 = row;
    int col3 = col + 1;
    if (is_valid_pos(row3, col3, width, height)) {
        uint8_t i3 = get_index(row3, col3, width, height);
        res = bitarray_flip(res, i3);
    }
    return res;
}

//solve the input file content
bool is_solvable(uint8_t width, uint8_t height, ba_ht_elem start){
    if(bitarray_equal(start->ba, bitarray_new())){
        //all lights off
        free(start);
        return true;
    }
    //create a new board hash table
    size_t capacity = (width * height) * 50;
    ht H = ba_ht_new(capacity);
    //board hash table elem enqueue Q
    queue Q = queue_new();
    enq(Q, (void *)start);
    //elem insert hash table
    ba_ht_insert(H, start);
    //queue is not empty
    while(!queue_empty(Q)){
        //dequeue front elem
        void* B = deq(Q);
        for(int row = 0; row <height; ++row){
            for(int col = 0; col < width; ++col){
                //touch the light at row:col
                uint8_t i = get_index(row, col, width, height);
                bitarray newbitarrry = press_button((ba_ht_elem)B, i,
                                                    row, col, width, height);
                //all lights off
                if(bitarray_equal(newbitarrry, bitarray_new())){
                    //output touch position
                    int sol_row = row;
                    int sol_col = col;
                    printf("%d:%d\n", sol_row, sol_col);
                    bitarray sol_bitarray = newbitarrry;
                    while(!bitarray_equal(sol_bitarray, start->ba)){
                        ba_ht_elem sol = xmalloc(sizeof(struct ba_ht_elem_base));
                        sol->ba = sol_bitarray;
                        sol->row_index_press = sol_row;
                        sol->col_index_press = sol_col;
                        uint8_t index = get_index(sol_row, sol_col, width, height);
                        sol_bitarray = press_button(sol, index, sol_row, sol_col, width, height);
                        ba_ht_elem e = ba_ht_lookup(H, &sol_bitarray);
                        sol_row = e->row_index_press;
                        sol_col = e->col_index_press;
                        if(!bitarray_equal(sol_bitarray, start->ba)){
                            //find target board
                            printf("%d:%d\n", e->row_index_press, 
                                e->col_index_press);
                        }
                        free(sol);
                    }
                    ht_free(H);
                    queue_free(Q, NULL);
                    return true;
                }
                //newbitarray after touch row:col is not in hash table
                if(ba_ht_lookup(H, &newbitarrry) == NULL){
                    ba_ht_elem newdata = xmalloc(sizeof(struct ba_ht_elem_base));
                    newdata->ba = newbitarrry;
                    newdata->row_index_press = row;
                    newdata->col_index_press = col;
                    ba_ht_insert(H, newdata);
                    enq(Q, (void *)newdata);
                }
            }
        }
    }
    //free the Hash table and queue
    ht_free(H);
    queue_free(Q, NULL);
    return false;
}